n=1000;
d=[198,276,974,388,435,817,424,649,959,180,70,662,283,526,58,973,773,770,981,578,416,566,28,645,236,772,874,772,105,69,691,558,362,790,8,798,813,880,193,334,460,800,136,250,630,714,105,55,755,36,634,751,379,723,71,384,623,365,767,727,555,944,713,357,40,700,565,533,98,120,306,597,291,594,793,302,708,695,780,58,912,685,907,930,220,193,91,155,221,563,979,223,319,902,883,802,719,827,436,347,557,927,467,391,644,661,732,147,280,560,4,158,498,334,880,829,554,860,69,792,8,44,812,190,419,97,754,617,57,330,43,769,71,306,318,487,385,441,637,53,966,996,898,728,545,932,486,355,689,717,851,325,194,260,713,52,847,698,388,727,807,974,697,617,324,798,701,306,311,920,40,109,190,897,998,819,66,238,875,391,635,344,726,361,305,71,133,461,665,427,87,577,658,928,908,349,45,818,519,733,541,124,63,326,479,477,814,738,349,639,691,382,661,811,637,354,875,47,236,619,165,964,830,797,97,324,497,333,290,922,884,892,468,179,637,244,683,456,427,143,828,625,414,757,281,67,306,632,667,879,799,357,188,803,321,717,254,244,1000,295,954,176,855,781,966,695,83,639,421,669,370,885,435,650,486,109,494,396,16,970,105,398,815,75,33,580,913,547,831,656,177,26,650,167,967,589,319,844,504,547,629,475,832,641,359,963,375,23,776,432,622,641,350,272,941,896,258,177,388,534,161,761,749,543,708,742,107,715,889,74,594,639,94,405,115,574,541,62,544,922,822,563,140,245,300,991,296,485,280,81,778,526,256,123,115,77,336,589,398,766,974,914,845,359,65,75,148,388,217,813,7,308,750,200,505,237,472,26,809,477,905,881,165,115,721,956,680,333,914,540,736,821,332,244,260,445,604,304,471,6,646,907,652,998,188,311,516,113,113,499,94,110,228,454,441,141,584,261,813,685,764,311,196,150,514,184,144,159,657,602,562,83,270,734,328,713,807,880,792,204,343,66,662,209,724,915,568,450,912,320,254,779,936,859,733,307,388,163,722,588,725,222,94,205,835,942,472,357,264,523,301,766,249,566,836,58,849,707,433,553,764,883,834,430,295,989,199,870,403,204,527,483,697,398,224,956,231,679,39,481,206,547,663,389,63,919,999,655,486,196,941,690,912,742,834,315,870,249,930,618,13,192,823,681,94,826,944,534,722,910,474,774,475,717,869,320,636,986,140,181,299,91,568,379,356,587,63,687,308,162,63,178,568,171,427,442,929,174,901,564,959,268,83,360,61,540,435,238,572,332,700,574,873,547,756,650,623,20,304,150,367,506,337,996,107,90,814,49,143,193,478,259,765,282,277,45,961,422,46,312,937,341,294,124,25,739,331,255,539,306,660,643,602,471,187,913,187,1000,434,408,304,792,108,973,397,183,3,776,253,68,32,558,382,155,264,377,766,632,91,523,786,78,384,615,367,270,995,448,525,755,783,613,338,126,868,775,656,996,853,822,423,638,40,744,108,274,91,154,496,832,264,383,647,759,581,946,257,297,693,265,465,355,728,963,150,329,215,483,70,463,522,567,695,927,523,524,408,815,6,218,702,169,507,573,306,933,101,623,553,809,737,916,777,159,637,406,709,660,386,287,407,758,755,366,64,71,401,703,217,489,405,728,228,984,687,74,781,929,724,847,623,128,153,284,264,94,498,373,715,939,111,460,131,217,105,8,604,95,343,611,555,975,294,641,500,983,718,749,833,864,358,916,781,314,836,172,23,890,964,313,248,579,824,130,712,885,979,918,920,866,417,859,276,655,576,454,995,900,5,492,225,876,198,240,228,209,544,81,17,775,379,423,234,949,787,566,802,239,857,684,227,546,651,715,950,516,265,712,869,292,323,884,187,807,594,272,939,809,547,194,624,901,398,35,107,745,687,42,229,331,156,795,671,825,251,462,593,347,619,518,180,843,447,8,794,300,53,360,167,526,475,96,147,11,418,871,715,580,544,183,187,330,264,946,513,167,317,909,925,939,918,367,448,89,66,909,92,573,440,103,512,947,6,796,448,989,516,437,256,338,357,296,687,710,126,467,590,665,359,857,17,192,852,418,220,889,339,790,785,266,956,597,479,205,632,161,518,722,65,101,358,717,696,924,359,452,291,106,19,231,666,76,368,248,718,136,467,828,372,464,997,415,918,558,236,379,47,44,638,532,174,193,645,450,66,667,311,492,236,299,509,371,889,256,279,261,91,581,875,510,981,787,222,830,338,850,53,8,225,992];